package com.example.graph;

import java.util.*;

/**
 * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
 * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 * 给你一个 n x n 的矩阵 isConnected ，
 * 其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而isConnected[i][j] = 0 表示二者不直接相连。
 * 返回矩阵中 省份 的数量。
 * <p>
 * 示例 1：
 * 输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
 * 输出：2
 * <p>
 * 示例 2：
 * 输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
 * 输出：3
 * <p>
 * 提示：
 * 1 <= n <= 200
 * n == isConnected.length
 * n == isConnected[i].length
 * isConnected[i][j] 为 1 或 0
 * isConnected[i][i] == 1
 * isConnected[i][j] == isConnected[j][i]
 */
public class Leetcode547_OfferII116_FindCircleNum {

    public static void main(String[] args) {

        int[][] isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
//        int[][] isConnected = {
//                {0, 0, 1, 0, 0},
//                {0, 0, 0, 0, 0},
//                {0, 0, 0, 1, 0},
//                {1, 1, 0, 1, 1},
//                {0, 0, 0, 0, 0}};

        System.out.println(new Solution().findCircleNum(isConnected));

    }

    /**
     * 本题相当于求图的连通分量
     *
     * 每次dfs遍历完毕即找到了一个连通分量
     * 将所有点全部遍历完毕需要几次dfs即有几个连通分量
     */
    static class Solution {

        public int findCircleNum(int[][] isConnected) {
            return findCircleNum3(isConnected);
        }

        /**
         * 并查集方式
         * @param matrix
         * @return
         */
        public int findCircleNum3(int[][] matrix) {
            UnionFindSet uf = new UnionFindSet(matrix.length);
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == 1) {
                        uf.union(i, j);
                    }
                }
            }
            return uf.count;
        }

        // 邻接矩阵dfs方式
        public int findCircleNum2(int[][] matrix) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
                return 0;
            boolean[] visited = new boolean[matrix.length];
            int count = 0;
            for (int i = 0; i < matrix.length; i++) {
                if (!visited[i]) {
                    dfs(matrix, visited, i);
                    count++;
                }
            }
            return count;
        }

        // 使用邻接表dfs遍历
        public int findCircleNum1(int[][] isConnected) {
            if (isConnected == null || isConnected.length == 0 || isConnected[0].length == 0)
                return 0;

            int res = 0;
            Map<Integer, List<Integer>> adj = new HashMap<>();
//            无向图adj构建
//            for (int i = 1; i < isConnected.length; i++) {
//                for (int j = 0; j < i; j++) {
//                    if (isConnected[i][j] == 1) {
//                        adj.computeIfAbsent(i, key -> new ArrayList<>()).add(j);
//                        adj.computeIfAbsent(j, key -> new ArrayList<>()).add(i);
//                    }
//                }
//            }

//            有向图adj构建
            for (int i = 0; i < isConnected.length; i++) {
                for (int j = 0; j < isConnected[0].length; j++) {
                    if (isConnected[i][j] == 1) {
                        adj.computeIfAbsent(i, key -> new ArrayList<>()).add(j);
//                        adj.computeIfAbsent(j, key -> new ArrayList<>()).add(i);
                    }
                }
            }
            boolean[] visited = new boolean[isConnected.length];

            for (int i = 0; i < visited.length; i++) {
                if (visited[i] == false) {
                    dfsTraverse(adj, i, visited);
                    res++;
                }
            }

            return res;
        }

        private void dfsTraverse(Map<Integer, List<Integer>> adj, int startNode, boolean[] visited) {
            if (adj.get(startNode) != null) {
                Iterator<Integer> iterator = adj.get(startNode).iterator();
                while (iterator.hasNext()) {
                    Integer tmp = iterator.next();
                    if (!visited[tmp]) {
                        visited[tmp] = true;
                        dfsTraverse(adj, tmp, visited);
                    }
                }
            }
        }

        /**
         * 邻接矩阵的dfs
         * 每次将上次等于1的y坐标作为下一次的x坐标，
         * 然后从0开始遍历本次的y坐标找到为1的地方
         *
         * 依次递归下去即可
         *
         * @param matrix
         * @param visited
         * @param x
         */
        public void dfs(int[][] matrix, boolean[] visited, int x) {
            for (int y = 0; y < matrix.length; y++) {
                if (matrix[x][y] == 1 && !visited[y]) {
                    visited[y] = true;
                    dfs(matrix, visited, y);
                }
            }
        }

        class UnionFindSet {
            int[] parents;
            int[] ranks;
            int count;

            public UnionFindSet(int nodeSize) {
                parents = new int[nodeSize];
                ranks = new int[nodeSize];
                count = nodeSize;
                Arrays.fill(ranks, 1);

                for (int i = 0; i < parents.length; i++) {
                    parents[i] = i;
                }
            }

            public int find(int node) {
                if (parents[node] != node)
                    parents[node] = find(parents[node]);

                return parents[node];
            }

            public void union(int node1, int node2) {
                int p1 = find(node1);
                int p2 = find(node2);
                if (p1 != p2) {
                    if (ranks[p1] > ranks[p2]) {
                        parents[p2] = p1;
                    } else if (ranks[p1] < ranks[p2]) {
                        parents[p1] = p2;
                    } else {
                        parents[p1] = p2;
                        ++ranks[p1];
                    }
                    --count;
                }
            }
        }
    }
}
